package cn.qyd.leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author 邱运铎
 *
 * @date 2024-03-27 9:19
 */
public class Graph {
    private List<int[]>[] graph;

    public Graph(int n, int[][] edges) {
        graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] edge : edges) {
            addEdge(edge);
        }
    }

    public void addEdge(int[] edge) {
        int x = edge[0];
        int y = edge[1];
        int cost = edge[2];
        graph[x].add(new int[]{y, cost});
    }

    public int shortestPath(int node1, int node2) {
        //权重优先级队列，存储node1节点到所能到达的节点路程中所有节点，按照到达节点的权重进行排序，权重最小的节点为首节点。
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int[] dict = new int[graph.length];
        Arrays.fill(dict,Integer.MAX_VALUE);
        //存放node1到所有能到达节点权重最小的路径，默认node1到自身为0.
        dict[node1] = 0;
        queue.offer(new int[]{0, node1});
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int cost = node[0], cur = node[1];

            if (cur == node2) {
                //这里返回dirt[cur] 和 cost,其实都一样，值都相同。
                return dict[cur];
            }

            for (int[] nextNode : graph[cur]) {
                int ncost = nextNode[1];
                int next = nextNode[0];
                if (dict[next] > cost + ncost) {
                    dict[next] = cost + ncost;
                    queue.add(new int[]{cost + ncost, next});
                }
            }
        }

        return  -1;
    }

    public static void main(String[] args) {
//        String str = "[[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]";
//        String replace = str.replace("[", "{");
//        System.out.println(replace.replace("]","}"));
        int[][] edges = new int[][]{{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
        Graph myGraph = new Graph(4, edges);
        System.out.println(myGraph.shortestPath(0,3));
        System.out.println(myGraph.shortestPath(3,2));
        myGraph.addEdge(new int[]{1,3,4});
        System.out.println(myGraph.shortestPath(0,3));
    }
}
